The state of the art in electronic purses in adequately described in part II of the (draft) European Standard EN 1546. The description as contained in that document is sumarised here and schematically given in FIG. 1; the draft standard contains a more detailed description and explicitly indicates the potential multiplicity of parties involved in the protocols which aspects have been omitted here for clarity. See also European patent 0,421,808-B1.
Referring to FIG. 1, an electronic purse operates In that in return for payment from a holder of a Value Carrying Device 1. A Value Guaranteeing Institution 4 is responsible for securely loading Balance 7 held in Value Carrying Device memory 52 of the Value Carrying Device 1 with a value using a value initializing protocol 12. The Value Carrying Device 1 is provided with a Value Carrying Device processor 50 connected to memory 52.
For the purpose of a payment the Value Carrying Device 1 which has a current value indicated as balance 7 engages with a Value Accepting Device 2 using a value transfer protocol 9, The Value Carrying Device 1 may be a tamper resistant device such as a smart card or may contain such a device that at least protects the integrity of the balance 7; the tamper resistant feature of the balance 7 is indicated in FIG. 1 by the double lines surrounding the balance 7. The basis of the value transfer protocol consists of a first xe2x80x9cclaimingxe2x80x9d message 13 from the Value Accepting Device 2 to the Value Carrying Device 1, fundamentally containing the amount to be transferred and optionally additional data which may possibly in part serve as a cryptographic challenge and a proving message 14 containing proof of debit of the balance 7. The cryptographic proof contained in the message 14 serves to authenticate the value transferred in the message and indirectly the correctness of processing inside the Value Carrying Device 1 and ultimately establishes a guarantee for refunding the transferred value by the Value Guaranteeing Institution 4. The Value Accepting Device 2 is provided with Value Accepting Device processor 51 connected to a Value Accepting Device memory 6. The Value Accepting Device processor 51 is, preferably, also tamper resistant.
The acceptance of the message depends on the verification by the Value Accepting Device 2 of the cryptographic proof contained in the message 14 upon which the Value Accepting Device 2 increases the value 8 held in its own secure storage 6. Alternative techniques may be used with equal result of accruing value in the Value Accepting Device 2, for instance one which allows value to be collected by storing every transaction individually in either secure or non secure storage in the Value Accepting Device. Such techniques may involve the exchange of more messages than those described in FIG. 2 which may contain additional data, but the net effect is the same: transfer of value. U.S. Pat. Nos. 4,996,711 and 5,131,039 of Chaum describe such possible protocols, mainly differing in the cryptographic techniques applied. These and other specific protocols are used in commercially available electronic purse smart card applications.
Periodically, for the purpose of recovering the values accepted from the Value Guaranteeing Institution 4, an Acquirer 3 is involved which may be an entity independent from the Value Guaranteeing Institution 4 or identical to it. The Acquirer 3 uses an acquiring protocol 10 to transfer information about the values accepted by the Value Accepting Device 2 during that period for storage and processing and as a result makes a payment 15 to the operator of the Value Accepting Device 2. The British patent application 9505397.1 (Transmo) describes a particular realisation of an acquiring protocol.
The Acquirer 3 may consolidate, by whatever means, value information from a multitude of Value Accepting Devices 2 and deduce the total value to be reclaimed from each Value Guaranteeing Institution 4 using a clearing and settlement protocol 11. As a result, a Value Guaranteeing Institution 4 makes a settlement 16 with the Acquirer 3 for the payments 15 made for the value issued by that particular institution which had been accepted by the Value Accepting Devices 2 as acquired by said Acquirer 3.
With electronic purse systems implemented according to the state of the art it is generally economically infeasible to store, communicate and electronically process individual transactions when they are in majority of small value, which is often the case. As a remedy, a tamper resistant security device 6. commonly known as xe2x80x9cSAMxe2x80x9d (=Security Application Module) that is provided as an integral component of every Value Accepting Device, is deployed into which individual payments are accumulated into a single value for subsequent processing by the Acquirer 3. Additionally the SAM is also used to hold security keys that when used in conjunction with a publicly known algorithm allow the Value Accepting Device 2 to verify in the value transfer protocol 9 the authenticity of the Value Carrying Device 1 and the value transferred; specifically to verify the correctness of the debit proof contained in message 14. The SAM 6 is thus a integral part of the security of the payment system and holds secret information common to the secret information held in each Value Carrying Device 1, it has to be secure against the revealing or alteration of its contents. If compromised by various forms of physical and or analytical attack, the SAM 6 can be made to reveal the secrets upon which the entire security of payment schemes using such techniques rely. These tamper resistance requirements for the SAM 6 adds to the complexity and cost of Value Accepting Device""s, to increased complexity of security management and increases the exposure to risks of misuse of the payment system.
One could use public key cryptographic algorithms to protect the value transfer protocol in implementations of an electronic purse according to the state of the art which would obviate, in principle, the need for SAM""s 6 as part of the Value Accepting Device 2 to authenticate the Value Carrying Device 1 and the value transferred. This restricts the exposure to risks of Misuse of the system. However, in general the amount of data required to be stored with each public key protected transaction is significantly large. The need to aggregate in the Value Carrying Device 1 is even greater than in alternative implementations. Again, where aggregation is required the Value Carrying Device 1 must contain a se cured component that can be trusted by the Value Guaranteeing Institution 4 or Acquirer 3 to perform the accumulation. The tamper resistance requirements for the Value Accepting Device 2 adds to the complexity and cost of the device and to increased complexity of security management in the system.
In purse systems implemented according to the state of the art the actual value transfer protocol 9 is complicated to ensure that failures in communications between Value Carrying Device 1 and Value Accepting Device 2 do not cause irrecoverable loss of value. Additional protocols may be implemented for recovery of value after interrupted communications. Fundamentally, with implementations according to the state of the art, the risk of irrecoverable loss of value can not be eliminated in full however complex the protocol. The added complexity in protocols needed to reach a sufficient level of practical reliable operation increases the implementation costs, increases the transaction duration and may lead to more complicated device usage handling, e.g. for explicit recovery protocols.
The object of the current invention is, firstly, to obviate the need for secure devices in Value Accepting Devices. secondly, to guarantee no irrecoverable loss of value, thirdly, to simplify the value transfer protocol, and fourthly, to make it technically and economically feasible to apply a single type of protocol for a wide range of electronic payment applications, with varying requirements in speed of transaction, means of communication and range of values to transfer. A further purpose of the current invention is to bring a level of privacy protection to rechargeable purse systems in a manner which before has only been possible with public key cryptography without the need for the lengthy and complex public key cryptographic computations.
The object of the present invention is obtained by a value transfer system comprising at least one Value Carrying Device and at least one Value Accepting Device being able to communicate with each other, the at least one Value Accepting Device comprising a Value Accepting Device memory for storing at least an aggregate value of previous accepted values and being arranged to transfer a claiming message representing at least a transaction value to said at least one Value Carrying Device, the at least one Value Carrying Device comprising a Value Carrying Device memory for storing at least a balance value and being arranged to transfer a proving message to said at least one Value Accepting Device, characterised in that the at least one Value Accepting Device is arranged to further include into the claiming message a previous aggregate value and a corresponding previously computed proving cryptogram;
the at least one Value Carrying Device is arranged to compute and include into the proving message at least one transaction proving cryptogram, computed on the basis of the previous aggregate value, the corresponding previously computed proving cryptogram and the transaction value, and
the at least one Value Carrying Device is arranged to compute the at least one transaction proving cryptogram only if it has established the correctness of the received previous aggregate value by using said corresponding previously computed cryptogram and after it has reduced the balance value with the transaction value.
Risk exposure limitation can easily be obtained by having keys shared by small sets of Value Carrying Devices instead of global key sharing with the associated risk of full system collapse in the event of key compromise. A system using keys shared by small sets is claimed in claim 2.
An other way of risk limitation may easily be obtained by reducing the maximum value of the resulting aggregate value, where the acquiring protocol resets the value. A system directed to such a risk limitation is claimed in claim 3.
Still, an other way of risk limitation may be easily obtained by reducing the maximum value of each individual transfer. A system directed to such a way of risk limitation is claimed in claim 4.
Still, a further way of risk limitation may be easily obtained by reducing the maximum number of transfers, that may be accepted by a device, where the acquiring protocol resets the count. A system directed to such a way of risk limitation is claimed in claim 5.
The present invention is also directed to a Value Carrying Device as part of the system defined above, which is arranged to communicate with at least one Value Accepting Device, said Value Carrying Device comprising a Value Carrying Device memory for storing at least a balance value and being arranged to receive a claiming message representing at least a transaction value and to transfer a proving message to said at least one Value Accepting Device, characterised in that the Value Carrying Device is arranged to receive through the claiming message a previous aggregate value and a corresponding previously computed proving cryptogram:
compute and include into the proving message at least one transaction proving cryptogram, computed on the basis of the previous aggregate value, the corresponding previously computed proving cryptogram and the transaction value, and
compute the at least one transaction proving cryptogram only if it has established the correctness of the received previous aggregate value by using said corresponding previously computed cryptogram and after it has reduced the balance value with the transaction value.
Moreover, the present invention is directed to a Value Accepting Device as part of the system defined above, which is arranged to communicate with at least one Value Carrying Device, said Value Accepting Device comprising a Value Accepting Device memory for storing at least an aggregate value of previous accepted values and being arranged to transfer a claiming message representing at least a transaction value to said at least one Value Carrying Device end to receive a proving message from said at least one Value Carrying Device, characterised in that
said Value Accepting Device is arranged to further include into the claiming message a previous aggregate value and a corresponding previously computed proving cryptogram in order to allow the at least one Value Carrying Device to compute and include into the proving message at least one transaction proving cryptogram, computed on the basis of the previous aggregate value, the corresponding previously computed proving cryptogram and the transaction value, and to allow the at least one Value Carrying Device to compute the at least one transaction proving cryptogram only if it has established the correctness of the received previous aggregate value by using said corresponding previously computed cryptogram and after it has reduced the balance value with the transaction value.
The present invention also relates to a method of cryptographically protecting a communication or a sequence of communications between a transmitter and a receiver, and of establishing a monotonic order in which messages are communicated or a strict monotonic change of numeric values contained in communicated messages characterised in that said communications include at least one number representing said monotonic order or representing said numeric values and cryptograms computed from the at least one number in an encoding using a xe2x80x9cPeanoxe2x80x9d number scheme as follows:
choosing a discrete maximum value for the encoding;
selecting a cryptographic one-way function that maps starting numbers consisting of a predetermined number of bits to object numbers consisting of the same predetermined number of bits a functional application to a number being defined as xe2x80x9csuccessor operationxe2x80x9d in the Peano number scheme;
selecting a random number consisting of said predetermined number of bits as zero element in the Peano number scheme;
determining a value encoded in a number as the value of a Peano number determined by repeated functional applications of the one-way function starting with the zero element until a result of the functional application of the one-way function equals a code number to be decoded, wherein a code word is found not to be a valid encoding if none of the results of applying repetitively for a number of times equal to the chosen discrete maximum value the cryptographic one-way function starting with the selected zero element equals the code word:
and in that the at least one transmitter is arranged to select said random number while keeping said random number confidential in order to warrant unconditional monotonicity of the message order or of the numeric values communicated.
Such a method effectively uses cryptographic encoding of monotonous series of data in one-way counters. Thus, secret keys used for encoding are based on a one-way scheme and can never be revealed by using reverse engineering techniques on data alone. Therefore, data can very securely be transmitted between a Value Carrying Device and a Value Accepting Device,
One possible value transfer system based on the method defined above and using one-way counters based on cryptograms stored in the Value Accepting Device memory, is claimed in claim 11. This embodiment improves over the method of plain cryptographic prooving cryptogram computation in that it allows use of simpler and cheaper shared key cryptography to prove a transfer where the value accepting device need not have available the secret to verify the proof. In addition, it provides a basis for efficient verifiable protection in the acquiring protocol.
An other possible embodiment of the method defined above is claimed in claim 13. The system of claim 13 does not need any additional cryptogram. It is more efficient than the embodiment mentioned above in that it reduces the amount of data to be transferred. Moreover, it is stronger as it does not have any confidential data stored in the Value Accepting Device. Moreover, it more elegantly includes the length (the discrete maximum value) of the one-way counter and additional data in the proving cryptogram.
An advantageous value transfer system, which is especially suited for payments in units. e.g., in telephone systems, toll road systems, public transport systems or in systems for consulting WWW pages, is claimed in claim 16:
The system as claimed in claim 17 shows further risk limitation by including a maximum value per transaction in a one-way counter based value cryptogram.
Claims 18 and 20 claim Value Accepting Devices for use in a value transfer system using one-way counter based value cryptograms, as defined above.
Claims 19 and 21 claim Value Carrying Devices for use in a value transfer system using one-way counter based value cryptograms, as defined above.
Value Accepting Devices may, advantageously, be implemented as a device with a memory only, for instance, a magnetic-strip card or memory-chip card.
The Value Carrying Devices may be implemented as start cards.
However, alternatively, the Value Carrying Devices and the Value Accepting Devices may be implemented together in an electronic device commonly known as a xe2x80x9cwalletxe2x80x9d.
The invention will be explained with reference to some drawings intended to illustrate and not to limit the scope of the invention.